import javafx.util.Pair;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
* @description: 994. 腐烂的橘子
* @author hewei
* @date 2022/9/27 14:17
* @version 1.0
*/

public class OrangesRotting {

    public static void main(String[] args) {

    }

    public int orangesRotting(int[][] grid) {
        HashSet<Integer> set = new HashSet<>();
        int count = 0;
        int[][] step = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Deque<Integer> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    ++count;
                    if (grid[i][j] == 2) {
                        int temp = i * n + j;
                        queue.add(temp);
                        set.add(temp);
                    }
                }
            }
        }
        int ans = -1;
        while (!queue.isEmpty()) {
            ++ans;
            int size = queue.size();
            while (size-- > 0) {
                Integer poll = queue.poll();
                for (int[] ints : step) {
                    int x = poll / n + ints[0];
                    int y = poll % n + ints[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != 0
                            && !set.contains(x * n + y)) {
                        queue.add(x * n + y);
                        set.add(x * n + y);
                    }
                }
            }
        }
        return set.size() == count ? (ans == -1 ? 0 : ans) : -1;
    }
}
